package com.xyhuo.leetcode.december;

import com.xyhuo.leetcode.common.TreeNode;

import java.util.*;

/**
 * 反转二叉树的奇数层
 * https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/
 *
 * @time 2023/12/15
 */
public class ReverseOddLevels {

    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root, 0);
        updateVal(root, 0);
        return root;
    }

    private Map<Integer, Deque<Integer>> map = new HashMap<>();

    private void dfs(TreeNode root, int floor) {
        if (null == root) {
            return;
        }
        dfs(root.left, floor + 1);
        if (floor % 2 == 1) {
            Deque<Integer> list;
            if (map.containsKey(floor)) {
                list = map.get(floor);
            } else {
                list = new ArrayDeque<>();
                map.put(floor, list);
            }
            list.add(root.val);
        }
        dfs(root.right, floor + 1);
    }

    private void updateVal(TreeNode root, int floor) {
        if (null == root) {
            return;
        }
        updateVal(root.left, floor + 1);
        if (floor % 2 == 1) {
            Deque<Integer> deque = map.get(floor);
            Integer last = deque.removeLast();
            root.val = last;
        }
        updateVal(root.right, floor + 1);
    }
}
